//
//  chemin.cpp
//  LOG2810
//
//  Created by Jules Thuillier on 11/03/2014.
//  Copyright (c) 2014 Jules Thuillier. All rights reserved.
//

#include "chemin.h"
#include <iostream>
#include <iterator>
#include <string>
#include <list>
#include <set>
#include <map>
#include <stdlib.h>     
#include <time.h> 

// Constructeurs

chemin::chemin(){
}

chemin::chemin(vector <vector <int> > matrice){
    matrix = matrice;
}

chemin::~chemin(){
    matrix.clear();
}


void chemin::set_matrix(vector <vector <int> > matrice){
    matrix = matrice;
}


void chemin::demander_chemin(){
    
	//on demande à l'utilisateur d'entrer au clavier les 2 points
	cout << endl << "Attention, les entrees au clavier sont les numeros de ligne dans la matrice \net non les numeros de points (ajouter 1)"<<endl;
    
    cout << endl << "point de depart : ";
    cin >> point_depart;
    
	while (point_depart<0 || point_depart >= matrix.size() || cin.fail() )
	{
        cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
		cout << "point de depart : ";
		cin >> point_depart;
	}
    
    cout << "point d'arrivee : ";
    cin >> point_arrivee;
    
	while (point_arrivee<0 || point_arrivee >= matrix.size() || point_arrivee == point_depart || cin.fail())
	{
        cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
		cout << "point d'arrivee : ";
		cin >> point_arrivee;
	}
    
    cout << endl << "agence de depart (1-2) : ";
    cin >> agence_depart;
    
	while ((agence_depart != 1 && agence_depart !=2) || cin.fail())
	{
        cin.clear();
		cout << "agence de depart (1-2) : ";
		cin >> agence_depart;
	}

    
    cout << "agence d'arrivee (1-2) : ";
    cin >> agence_arrivee;
    
	while ((agence_arrivee != 1 && agence_arrivee !=2) || cin.fail())
	{
        cin.clear();
		cout << "agence d'arrivee (1-2) : ";
		cin >> agence_arrivee;
	}

}


// RF2

void chemin::calculer_chemin(){
    
    demander_chemin();
    bool exist = ask_existance(point_depart, point_arrivee, agence_depart, agence_arrivee);
    
    if(exist){
        cheminpluscourt (point_depart, point_arrivee, agence_depart,agence_arrivee);
    }
}



bool chemin::ask_existance(int &pointDepart, int& pointArrivee, int& agenceDepart, int& agenceArrivee ){
    
    //booléen renvoyé à la fin
	bool existe= false;
	   
	//on vérifie s'il n'y a pas un chemin direct :
	if (verif_existance(point_depart,point_arrivee))
		existe = true;
    
	//sinon, on verifie s'il existe un chemin indirect
	else
	{
		//on crée un liste Y (liste permet d'ajouter au début facilement) contenant le point "depart"
		std::list <int> malistedepart;
		malistedepart.push_back(point_depart);
        
		//on crée un set X (set permet de faire un "find") vide au départ que l'on remplit des points visités
		std::set <int> malistefin;
        
		//on visite chaque point tant qu'on est pas arrivé au point arrivé ou qu'il reste des points à visiter dans Y
		while (!malistedepart.empty() && !existe)
		{
			
			//Enlever a Y son premier element x et le rajouter a X ;
			int element = malistedepart.front();
			
            
			malistefin.insert(element);
			malistedepart.pop_front();
            
			//Rajouter en tete de Y les voisins y de x non deja dans X ∪ Y ;
			for (int i=0;i<matrix.size();i++)
			{
				if(i!=element && verif_existance(i,element) && find(malistefin.begin(),malistefin.end(),i)==malistefin.end() && !appartient(i,malistedepart))
				{
					
					malistedepart.push_front(i);
					if (verif_existance(i,point_arrivee))
					{
                        existe = true ;
                        i = (int)matrix.size();
                    }
				}
			}
		}
	}
    
	if (existe){
		cout << endl << "Il existe un chemin entre P" << point_depart+1 << " et P" <<point_arrivee+1 << endl;
        return true;
    }
	else {
		cout << endl << "Il n'existe aucun chemin entre P" << point_depart+1 << " et P"<<point_arrivee+1 << endl;
        return false;
    }
}



bool chemin::verif_existance(int depart,int arrivee){
	if (depart < arrivee)
	{
		//on a un "+2" car les colonnes associées aux lignes sont décalés de 2 (exemple : P1 est à la ligne 0 mais à la colonne 2)
		//cela est dû à la présence de 2 colonne pour les agences
		if ( matrix [arrivee] [depart+2] != 0 )
			return true;
		else
			return false;
	}
	else
	{
		if ( matrix [depart] [arrivee+2] != 0 )
			return true;
		else
			return false;
	}
}

bool chemin::appartient(int object, std::list<int> liste){
	bool temp = false;
	std::list<int>::iterator it=liste.begin();
	//on parcourt la liste à la recherche de l'objet
	while (it != liste.end())
	{
		if(*it == object)
			temp = true;
		it++;
	}
	
	return temp;
}


// RF3 & RF4


void chemin::cheminpluscourt(int &pointDepart, int& pointArrivee, int& agenceDepart, int& agenceArrivee ){
    
	//on ajoute les couts des distance entre A2 et le points de départ et d'arrivée
	double cout_minimum = 0;
	cout_minimum += matrix [point_depart] [agenceDepart-1] ;
	cout_minimum += matrix [point_arrivee] [agenceArrivee-1] ;
    
	//dans la map, l'index (1er int) est le point que l'on étudie,
	std::map<int,val_point> coutparpoint;
	std::map<int,val_point>::iterator it1, it2;
    
	//on initialise le cout de chaque point à 5000 (on ne peut pas mettre l'infini donc un mets une valeure très élevée)
	//on laisse la valeur du point de départ à 0
	for (int i=0; i<matrix.size();i++)
	{
		if (i==point_depart)
		{
			std::vector<int> vect_depart ;
			vect_depart.push_back(point_depart);
			val_point map_depart;
			map_depart.valeurpoint=0;
			map_depart.vecteurpoints=vect_depart;
			coutparpoint [i] = map_depart ;
		}
		else
		{
			//les vecteur seront créés au moment où les points seront visités
			val_point map_temp;
			map_temp.valeurpoint = 5000;
			coutparpoint [i] = map_temp ;
		}
	}
    
    
    
    //on crée une liste Y (liste permet d'ajouter au début facilement) contenant le point "depart"
    std::list <int> malistedepart;
    malistedepart.push_back(point_depart);
    
    //on crée un set X (set permet de faire un "find") vide au départ que l'on remplit des points visités
    std::set <int> malistefin;
    
    //on visite chaque point tant qu'on est pas arrivé au point arrivé ou qu'il reste des points à visiter dans Y
    while (!malistedepart.empty())
    {
        
        //Range la liste selon le cout de chaque element
        //c'est pas simple, mais ça marche !
        std::list <int> listetemppourrangement ;
        while(!malistedepart.empty())
        {
            double minimum=5000;
            int valeurtemp=0;
            std::list <int>::iterator ittemp2 ;
            
            for (std::list <int>::iterator ittemp = malistedepart.begin(); ittemp != malistedepart.end();ittemp++)
            {
                
                it1=coutparpoint.find(*ittemp);
                if((it1->second).valeurpoint<minimum)
                {
                    minimum = (it1->second).valeurpoint;
                    valeurtemp=*ittemp;
                    ittemp2=ittemp;
                }
            }
            malistedepart.erase(ittemp2);
            listetemppourrangement.push_back(valeurtemp);
        }
        malistedepart=listetemppourrangement;
        listetemppourrangement.clear();
        
        //Enlever a Y son premier element x et le rajouter a X ;
        int element = malistedepart.front();
        
        malistefin.insert(element);
        malistedepart.pop_front();
        
        //Rajouter en tete de Y les voisins y de x non deja dans X ∪ Y ;
        //Calculer la valeur minimale pour se rendre à chaque points depuis la point de départ
        for (int i=0;i<matrix.size();i++)
        {
			
            if(i!=element && verif_existance(i,element) && find(malistefin.begin(),malistefin.end(),i)==malistefin.end())
            {
                if(!appartient(i,malistedepart)){
                    malistedepart.push_front(i);
                }
                it1 = coutparpoint.find(element);
                it2 = coutparpoint.find(i);
                double temp1 = (it1->second).valeurpoint;
                if (i < element)
                {
                    temp1 += matrix [element] [i+2] ;
                }
                else 
                {
                    temp1 += matrix [i] [element+2] ;
                }
                double temp2 = (it2->second).valeurpoint;
                
                if (temp1 < temp2)
                {
                    (it2->second).valeurpoint=temp1;
                    (it2->second).vecteurpoints=(it1->second).vecteurpoints;
                    (it2->second).vecteurpoints.push_back(i);
                }
                
            }
            
        }
    }
    
    //on récupère le cout et le vecteur sur le point d'arrivé affin de les afficher
    it1 = coutparpoint.find(point_arrivee);
    cout_minimum += (it1->second).valeurpoint;
   
    
    // Affichage different si les agences de depart et d'arrivee sont les meme ou non
    if (agenceDepart == agenceArrivee) {
        cout << endl << "Le chemin le plus court entre P" << point_depart+1 << " et P" << point_arrivee+1 << " en partant et revenant a une meme \nagence est :" << endl;
    }
    else {
    cout << endl << "Le chemin le plus court entre P" << point_depart+1 << " et P" << point_arrivee+1 << " en changeant d agence est :" << endl;
    }
    
    cout << endl <<"A"<<agenceDepart<<" -> ";
    
    for (int i=0; i<(it1->second).vecteurpoints.size();i++)
    {
        cout << "P" << (it1->second).vecteurpoints[i]+1 << " -> ";
    }
    
    cout << "A" << agenceArrivee << endl << endl << "avec un cout de : " << cout_minimum << endl;
}




//RF 5


void chemin::afficher_sommets(){

	//random pour savoir à quel sommet commencer 
	srand (time(NULL));
	int random = rand() % matrix.size();

	//on crée une liste Y (liste permet d'ajouter au début facilement) contenant le point random
    std::list <int> malistedepart;
    malistedepart.push_back(random);
	std::vector <int> listeaafficher;
    listeaafficher.push_back(random);
    
    //on crée un set X (set permet de faire un "find") vide au départ que l'on remplit des points visités
    std::set <int> malistefin;
    
    //on visite chaque point tant qu'on est pas arrivé au point arrivé ou qu'il reste des points à visiter dans Y
    while (!malistedepart.empty())
    {
        
        //Enlever a Y son premier element x et le rajouter a X ;
        int element = malistedepart.front();
        
        malistefin.insert(element);
        malistedepart.pop_front();
        
        //Rajouter en tete de Y les voisins y de x non deja dans X ∪ Y ;
        for (int i=0;i<matrix.size();i++)
        {
			
            if(i!=element && verif_existance(i,element) && find(malistefin.begin(),malistefin.end(),i)==malistefin.end() && !appartient(i,malistedepart))
            {
                malistedepart.push_front(i);
                listeaafficher.push_back(i);
                
            }
            
        }
    }

	cout << endl << "La liste des sommets est : "<< endl;
    
	cout << "P" << listeaafficher[0]+1;

	for (int i=1; i<listeaafficher.size();i++)
    {
		cout << " - " << "P" << listeaafficher[i]+1;
    }
    cout << endl;

}